package com.zjj.algorithm.learning.leetcode.tree;

/**
 * 100. 相同的树 简单
 * 给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。
 * <p>
 * 如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
 * <p>
 * 输入：p = [1,2,3], q = [1,2,3]
 *    1               1
 * 2    3           2   3
 * 输出：true
 * <p>
 * 输入：p = [1,2], q = [1,null,2]
 *   1                  1
 * 2                      2
 * 输出：false
 * <p>
 * 输入：p = [1,2,1], q = [1,1,2]
 *   1                1
 * 2  1             1  2
 * 输出：false
 *
 * @author zjj_admin
 * @date 2022/11/22 10:14
 */
public class SameTree {

    public static void main(String[] args) {


        TreeNode node1 = new TreeNode(1);
        TreeNode node2 = new TreeNode(2);
        TreeNode node3 = new TreeNode(1);

        TreeNode node4 = new TreeNode(1);
        TreeNode node5 = new TreeNode(1);
        TreeNode node6 = new TreeNode(2);
        TreeNode node7 = new TreeNode(8);

        node1.left = node2;
        node1.right = node3;


        node4.left = node5;
        node4.right = node6;

        boolean res1 = isSameTree(node1, node4);
        System.out.println("res1 = " + res1);

//        boolean res2 = isSameTree(node4, node6);
//        System.out.println("res2 = " + res2);


    }


    /**
     * 时间
     * 0 ms
     * 击败
     * 100%
     * 内存
     * 38.8 MB
     * 击败
     * 72%
     *
     * @param p
     * @param q
     * @return
     */
    public static boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) {
            return true;
        }
        if (p == null || q == null) {
            return false;
        }
        //只要节点的数据不相等，就直接返回null
        if (p.val != q.val) {
            return false;
        } else {
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }

    }
}
